/*
description:从后边开始找比基准小的值停下来
从前边开始找到比基准大的值停下来
每次找到左边比基准值大，右边比基准值小就行
快速排序还有个(挖坑法)
 */

public class test {

    public static void print(int[] array){ //打印方法
        for (int i = 0;i < array.length;i++){
            System.out.print(array[i]+" ");
        }
    }

    public static void main(String[] args) {
        System.out.println("hello quicksort!");
        int[] array = {6,1,2,5,4,3,9,7,10,8};
        quicksort(array);
        print(array);
    }

    public static void quicksort(int[] array){ //快速排序
        quick(array,0, array.length-1);
    }

    private static void quick(int[] array,int start,int end){ //分层
        if (start >= end){
            return;
        }
        int pivot = partition(array,start,end);
        quick(array,start, pivot-1);
        quick(array,pivot+1,end);
    }

    private static int partition(int[] array,int left,int right){ //排序过程
        int tmp = array[left];
        int tmpLeft = left;
        while (left < right){
            while (left < right && array[right] >= tmp){
                right--;
            }

            //可以用挖坑法（这个判断没必要加，但是加了也无妨）
                array[tmpLeft] = array[right];  // 用right的值填坑
                tmpLeft = right;                // right位置形成新坑


            while (left < right && array[left] <= tmp){
                left++;
            }
            //swap(array, left, right);//可以改成挖坑法

            //改成挖坑法就是这个代码块
                array[tmpLeft] = array[left];   // 用left的值填坑
                tmpLeft = left;                 // left位置形成新坑


        }
        //swap(array, tmpLeft, right);//挖坑法完成后这里交换可以改成把原来的基准放到坑里

        array[tmpLeft] = tmp;// 将基准值填入最终的坑位

        return left;
    }

    public static void swap(int[] array,int left,int right){ //交换方法
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }

}
